// File:       algorithm.c++
// Version:    1.00
// Author:     Acorn C/C++ port (c) Miles Sabin, 1996
// Purpose:    approximation to ANSI C++ standard algorithms

// Copyright (c) 1994
// Hewlett-Packard Company
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Hewlett-Packard Company makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.

// Change log:
//  28/12/96   v. 1.00
//   2/01/97   Added heap algorithms.
//             Added remaining HP algorithms.
//   3/01/97   Added find_end().
//             Added find_first_of().
//             Added two more search() variants.
//   9/01/97   Renamed new search variants to search_n to work around
//               CFront template fn overloading problem.
//  10/01/97   Some tweaking to unique_copy().
//             min() and max() now return by value rather than by
//               reference to suppress warnings in merge().
//  31/03/97   Added swap_ranges().
//   2/04/97   Removed some spurious inlines.

#include "algorithm.h"

#include "iterator.h"
#include "memory.h"        // for raw_storage_iterator<T> and temporary buffers


// Implementation of non-modifying sequence operations

// find_end

template<class RandomAccessIterator1, class ForwardIterator2, class Distance1, class Distance2>
RandomAccessIterator1
  __find_end
    (RandomAccessIterator1 first1, RandomAccessIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     Distance1*, Distance2*, random_access_iterator_tag)
{
  Distance1 len1 = 0;
  distance(first1, last1, len1);
  Distance2 len2 = 0;
  distance(first2, last2, len2);

  if(len2 == 0 || len2 > len1)
    return last1-1;

  for(RandomAccessIterator1 i = last2-(len2-1); i != first1;)
  {
    --i;

    if(*i == *first2)
    {
      RandomAccessIterator1 j1 = i;
      ForwardIterator2 j2 = first2;

      while(++j2 != last2 && *++j1 == *j2);

      if(j2 == last2)
        return j1;
    }
  }

  return last1;
}

template<class BidirectionalIterator1, class ForwardIterator2, class Distance1, class Distance2>
BidirectionalIterator1
  __find_end
    (BidirectionalIterator1 first1, BidirectionalIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     Distance1*, Distance2*, bidirectional_iterator_tag)
{
  Distance1 len1 = 0;
  distance(first1, last1, len1);
  Distance2 len2 = 0;
  distance(first2, last2, len2);

  if(len2 == 0 || len2 > len1)
  {
    BidirectionalIterator1 p = last1;
    return --p;
  }

  BidirectionalIterator1 i = first1;
  advance(i, len1-(len2-1));

  while(i != first1)
  {
    --i;

    if(*i == *first2)
    {
      BidirectionalIterator1 j1 = i;
      ForwardIterator2 j2 = first2;

      while(++j2 != last2 && *++j1 == *j2);

      if(j2 == last2)
        return j1;
    }
  }

  return last1;
}

template<class ForwardIterator1, class ForwardIterator2, class Distance1, class Distance2>
ForwardIterator1
  __find_end
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     Distance1*, Distance2*, forward_iterator_tag)
{
  Distance1 len1 = 0;
  distance(first1, last1, len1);
  Distance2 len2 = 0;
  distance(first2, last2, len2);

  if(len2 == 0 || len2 > len1)
  {
    ForwardIterator1 p = first1;
    while(++first1 != last1)
      ++p;

    return p;
  }

  for(Distance1 i = len1-(len2-1); i != 0;)
  {
    --i;

    ForwardIterator1 j1 = first1;
    advance(j1, i);

    if(*j1 == *first2)
    {
      ForwardIterator2 j2 = first2;

      while(++j2 != last2 && *++j1 == *j2);

      if(j2 == last2)
        return j1;
    }
  }

  return last1;
}

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
  find_end
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2)
{
  return __find_end(first1, last1, first2, last2, distance_type(first1), distance_type(first2), iterator_category(first1));
}

template<class RandomAccessIterator1, class ForwardIterator2, class Predicate, class Distance1, class Distance2>
RandomAccessIterator1
  __find_end
    (RandomAccessIterator1 first1, RandomAccessIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     Predicate pred,
     Distance1*, Distance2*, random_access_iterator_tag)
{
  Distance1 len1 = 0;
  distance(first1, last1, len1);
  Distance2 len2 = 0;
  distance(first2, last2, len2);

  if(len2 == 0 || len2 > last1-first1)
    return last1-1;

  for(RandomAccessIterator1 i = last2-(len2-1); i != first1;)
  {
    --i;

    if(pred(*i, *first2))
    {
      RandomAccessIterator1 j1 = i;
      ForwardIterator2 j2 = first2;

      while(++j2 != last2 && pred(*++j1, *j2));

      if(j2 == last2)
        return j1;
    }
  }

  return last1;
}

template<class BidirectionalIterator1, class ForwardIterator2, class Predicate, class Distance1, class Distance2>
BidirectionalIterator1
  __find_end
    (BidirectionalIterator1 first1, BidirectionalIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     Predicate pred,
     Distance1*, Distance2*, bidirectional_iterator_tag)
{
  Distance1 len1 = 0;
  distance(first1, last1, len1);
  Distance2 len2 = 0;
  distance(first2, last2, len2);

  if(len2 == 0 || len2 > len1)
  {
    BidirectionalIterator1 p = last1;
    return --p;
  }


  BidirectionalIterator1 i = first1;
  advance(i, len1-(len2-1));

  while(i != first1)
  {
    --i;

    if(pred(*i, *first2))
    {
      BidirectionalIterator1 j1 = i;
      ForwardIterator2 j2 = first2;

      while(++j2 != last2 && pred(*++j1, *j2));

      if(j2 == last2)
        return j1;
    }
  }

  return last1;
}

template<class ForwardIterator1, class ForwardIterator2, class Predicate, class Distance1, class Distance2>
ForwardIterator1
  __find_end
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     Predicate pred,
     Distance1*, Distance2*, forward_iterator_tag)
{
  Distance1 len1 = 0;
  distance(first1, last1, len1);
  Distance2 len2 = 0;
  distance(first2, last2, len2);

  if(len2 == 0 || len2 > len1)
  {
    ForwardIterator1 p = first1;
    while(++first1 != last1)
      ++p;

    return p;
  }

  for(Distance1 i = len1-(len2-1); i != 0;)
  {
    --i;

    ForwardIterator1 j1 = first1;
    advance(j1, i);

    if(pred(*j1, *first2))
    {
      ForwardIterator2 j2 = first2;

      while(++j2 != last2 && pred(*++j1, *j2));

      if(j2 == last2)
        return j1;
    }
  }

  return last1;
}

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
  find_end
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     BinaryPredicate pred)
{
  return __find_end(first1, last1, first2, last2, pred, distance_type(first1), distance_type(first2), iterator_category(first1));
}


// find_first_of

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
  find_first_of
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2)
{
  for(; first1 != last1; ++first1)
  {
    ForwardIterator2 c = first2;
    for(; c != last2 && *first1 != *c; ++c);
    if(c != last2)
      break;
  }

  return first1;
}

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
  find_first_of
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     BinaryPredicate pred)
{
  for(; first1 != last1; ++first1)
  {
    ForwardIterator2 c = first2;
    for(; c != last2 && !pred(*first1,*c); ++c);
    if(c != last2)
      break;
  }

  return first1;
}


// adjacent_find

template<class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)
{
  if(first == last)
    return last;

  ForwardIterator next = first;
  while(++next != last)
  {
    if(*first == *next)
      return first;
    first = next;
  }
  return last;
}

template<class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred)
{
  if(first == last)
    return last;

  ForwardIterator next = first;
  while(++next != last)
  {
    if(binary_pred(*first, *next))
      return first;
    first = next;
  }
  return last;
}


// search

template<class ForwardIterator1, class ForwardIterator2, class Distance1, class Distance2>
ForwardIterator1
  __search
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     Distance1*, Distance2*)
{
  Distance1 d1 = 0;
  distance(first1, last1, d1);
  Distance2 d2 = 0;
  distance(first2, last2, d2);

  if(d1 < d2)
    return last1;

  ForwardIterator1 current1 = first1;
  ForwardIterator2 current2 = first2;

  while(current2 != last2)
    if(*current1++ != *current2++)
    {
      if(d1 == d2)
        return last1;
      else
      {
        --d1;
        current1 = ++first1;
        current2 = first2;
      }
    }

  return (current2 == last2 ? first1 : last1);
}

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
  search
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2)
{
  return __search(first1, last1, first2, last2, distance_type(first1), distance_type(first2));
}

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate, class Distance1, class Distance2>
ForwardIterator1
  __search
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     BinaryPredicate binary_pred,
     Distance1*, Distance2*)
{
  Distance1 d1 = 0;
  distance(first1, last1, d1);
  Distance2 d2 = 0;
  distance(first2, last2, d2);

  if(d1 < d2)
    return last1;

  ForwardIterator1 current1 = first1;
  ForwardIterator2 current2 = first2;

  while(current2 != last2)
    if(!binary_pred(*current1++, *current2++))
    {
      if(d1 == d2)
        return last1;
      else
      {
        --d1;
        current1 = ++first1;
        current2 = first2;
      }
    }

  return (current2 == last2 ? first1 : last1);
}

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
  search
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     BinaryPredicate binary_pred)
{
  return __search(first1, last1, first2, last2, binary_pred, distance_type(first1), distance_type(first2));
}

template<class ForwardIterator1, class Size, class T, class Distance1>
ForwardIterator1
  __search_n
    (ForwardIterator1 first1, ForwardIterator1 last1,
     Size count, T const& value,
     Distance1*)
{
  Distance1 d1 = 0;
  distance(first1, last1, d1);

  if(d1 < count)
    return last1;

  ForwardIterator1 current1 = first1;
  Size current2 = 0;

  while(current2 != count)
    if(*current1++ == value)
      ++current2;
    else
    {
      if(d1 == count)
        return last1;
      else
      {
        --d1;
        current1 = ++first1;
        current2 = 0;
      }
    }

  return (current2 == count ? first1 : last1);
}

template<class ForwardIterator, class Size, class T>
ForwardIterator
  search_n(ForwardIterator first, ForwardIterator last, Size count, T const& value)
{
  return __search_n(first, last, count, value, distance_type(first));
}

template<class ForwardIterator1, class Size, class T, class BinaryPredicate, class Distance1>
ForwardIterator1
  __search_n
    (ForwardIterator1 first1, ForwardIterator1 last1,
     Size count, T const& value,
     BinaryPredicate pred,
     Distance1*)
{
  Distance1 d1 = 0;
  distance(first1, last1, d1);

  if(d1 < count)
    return last1;

  ForwardIterator1 current1 = first1;
  Size current2 = 0;

  while(current2 != count)
    if(pred(*current1++, value))
      ++current2;
    else
    {
      if(d1 == count)
        return last1;
      else
      {
        --d1;
        current1 = ++first1;
        current2 = 0;
      }
    }

  return (current2 == count ? first1 : last1);
}

template<class ForwardIterator, class Size, class T, class BinaryPredicate>
ForwardIterator
  search_n(ForwardIterator first, ForwardIterator last, Size count, T const& value, BinaryPredicate pred)
{
  return __search_n(first, last, count, value, pred, distance_type(first));
}


// Implementation of mutating sequence operations

// remove

template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, T const& value)
{
  first = find(first, last, value);
  ForwardIterator next = first;
  return (first == last ? first : remove_copy(++next, last, first, value));
}

template<class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred)
{
  first = find_if(first, last, pred);
  ForwardIterator next = first;
  return (first == last ? first : remove_copy_if(++next, last, first, pred));
}


// unique

template<class InputIterator, class ForwardIterator>
ForwardIterator
  __unique_copy_forward
    (InputIterator first, InputIterator last, ForwardIterator result)
{
  *result = *first;
  while(++first != last)
    if(*result != *first)
      *++result = *first;
  return ++result;
}

template<class InputIterator, class RandomAccessIterator>
inline RandomAccessIterator
  __unique_copy
    (InputIterator first, InputIterator last, RandomAccessIterator result, random_access_iterator_tag)
{
  return __unique_copy_forward(first, last, result);
}

template<class InputIterator, class BidirectionalIterator>
inline BidirectionalIterator
  __unique_copy
    (InputIterator first, InputIterator last, BidirectionalIterator result, bidirectional_iterator_tag)
{
  return __unique_copy_forward(first, last, result);
}

template<class InputIterator, class ForwardIterator>
inline ForwardIterator
  __unique_copy
    (InputIterator first, InputIterator last, ForwardIterator result, forward_iterator_tag)
{
  return __unique_copy_forward(first, last, result);
}

template<class InputIterator, class OutputIterator, class T>
OutputIterator
  __unique_copy_output(InputIterator first, InputIterator last, OutputIterator result, T*)
{
  T value = *first;
  *result = value;
  while(++first != last)
    if(value != *first)
    {
      value = *first;
      *++result = value;
    }

  return ++result;
}

template<class InputIterator, class OutputIterator>
inline OutputIterator
  __unique_copy(InputIterator first, InputIterator last, OutputIterator result, output_iterator_tag)
{
  return __unique_copy_output(first, last, result, value_type(first));
}

template<class InputIterator, class OutputIterator>
OutputIterator
  unique_copy(InputIterator first, InputIterator last, OutputIterator result)
{
  if(first == last)
    return result;

  return __unique_copy(first, last, result, iterator_category(result));
}

template<class InputIterator, class ForwardIterator, class BinaryPredicate>
ForwardIterator
  __unique_copy_forward
    (InputIterator first, InputIterator last, ForwardIterator result,
     BinaryPredicate binary_pred)
{
  *result = *first;
  while(++first != last)
    if(!binary_pred(*result, *first))
      *++result = *first;

  return ++result;
}

template<class InputIterator, class RandomAccessIterator, class BinaryPredicate>
inline RandomAccessIterator
  __unique_copy
    (InputIterator first, InputIterator last, RandomAccessIterator result,
     BinaryPredicate binary_pred, random_access_iterator_tag)
{
  return __unique_copy_forward(first, last, result, binary_pred);
}

template<class InputIterator, class BidirectionalIterator, class BinaryPredicate>
inline BidirectionalIterator
  __unique_copy
    (InputIterator first, InputIterator last, BidirectionalIterator result,
     BinaryPredicate binary_pred, bidirectional_iterator_tag)
{
  return __unique_copy_forward(first, last, result, binary_pred);
}

template<class InputIterator, class ForwardIterator, class BinaryPredicate>
inline ForwardIterator
  __unique_copy
    (InputIterator first, InputIterator last, ForwardIterator result,
     BinaryPredicate binary_pred, forward_iterator_tag)
{
  return __unique_copy_forward(first, last, result, binary_pred);
}

template<class InputIterator, class OutputIterator, class BinaryPredicate, class T>
OutputIterator
  __unique_copy_output
    (InputIterator first, InputIterator last, OutputIterator result,
     BinaryPredicate binary_pred, T*)
{
  T value = *first;
  *result = value;
  while(++first != last)
    if(!binary_pred(value, *first))
    {
      value = *first;
      *++result = value;
    }

  return ++result;
}

template<class InputIterator, class OutputIterator, class BinaryPredicate>
inline OutputIterator
  __unique_copy
    (InputIterator first, InputIterator last, OutputIterator result,
     BinaryPredicate binary_pred, output_iterator_tag)
{
  return __unique_copy_output(first, last, result, binary_pred, value_type(first));
}

template<class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator
  unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred)
{
  if(first == last)
    return result;

  return __unique_copy(first, last, result, binary_pred, iterator_category(result));
}

template<class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last)
{
  first = adjacent_find(first, last);
  return unique_copy(first, last, first);
}

template<class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred)
{
  first = adjacent_find(first, last, binary_pred);
  return unique_copy(first, last, first, binary_pred);
}


// reverse

template<class BidirectionalIterator>
void __reverse(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag)
{
  while(true)
    if(first == last || first == --last)
      return;
    else
      iter_swap(first++, last);
}

template<class RandomAccessIterator>
void __reverse(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag)
{
  while(first < last)
    iter_swap(first++, --last);
}

template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last)
{
   __reverse(first, last, iterator_category(first));
}

template<class BidirectionalIterator, class OutputIterator>
OutputIterator
  reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result)
{
  while(first != last)
    *result++ = *--last;

  return result;
}


// rotate

template<class ForwardIterator, class Distance>
void
  __rotate
    (ForwardIterator first, ForwardIterator middle, ForwardIterator last,
     Distance*, forward_iterator_tag)
{
  for(ForwardIterator i = middle; ;)
  {
    iter_swap(first++, i++);
    if(first == middle)
    {
      if(i == last)
        return;
      middle = i;
    }
    else if(i == last)
      i = middle;
  }
}

template<class BidirectionalIterator, class Distance>
void
  __rotate
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
     Distance*, bidirectional_iterator_tag)
{
  reverse(first, middle);
  reverse(middle, last);
  reverse(first, last);
}

template<class EuclideanRingElement>
EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n)
{
  while(n != 0)
  {
    EuclideanRingElement t = m%n;
    m = n;
    n = t;
  }

  return m;
}

template<class RandomAccessIterator, class Distance, class T>
void
  __rotate_cycle
    (RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator initial,
     Distance shift, T*)
{
  T value = *initial;
  RandomAccessIterator ptr1 = initial;
  RandomAccessIterator ptr2 = ptr1+shift;

  while(ptr2 != initial)
  {
    *ptr1 = *ptr2;
    ptr1 = ptr2;

    if(last-ptr2 > shift)
      ptr2 += shift;
    else
      ptr2 = first+(shift-(last-ptr2));
  }

  *ptr1 = value;
}

template<class RandomAccessIterator, class Distance>
void
  __rotate
    (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last,
     Distance*, random_access_iterator_tag)
{
  Distance n = __gcd(last-first, middle-first);

  while(n--)
    __rotate_cycle(first, last, first+n, middle-first, value_type(first));
}

template<class ForwardIterator>
void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
{
  if(first == middle || middle == last)
    return;

  __rotate(first, middle, last, distance_type(first), iterator_category(first));
}

template<class ForwardIterator, class OutputIterator>
OutputIterator
  rotate_copy
    (ForwardIterator first, ForwardIterator middle, ForwardIterator last,
     OutputIterator result)
{
  return copy(first, middle, copy(middle, last, result));
}


// random_shuffle

extern unsigned long __long_random(unsigned long limit);

template<class RandomAccessIterator, class Distance>
void __random_shuffle(RandomAccessIterator first, RandomAccessIterator last, Distance*)
{
  if(first == last)
    return;

  for(RandomAccessIterator i = first+1; i != last; ++i)
    iter_swap(i, first+Distance(__long_random((i-first)+1)));
}

template<class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last)
{
  __random_shuffle(first, last, distance_type(first));
}

template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand)
{
  if(first == last)
    return;

  for(RandomAccessIterator i = first+1; i != last; ++i)
    iter_swap(i, first+rand((i-first)+1));
}

// partition operations

// partition

template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
  partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred)
{
  while(true)
  {
    while(true)
      if(first == last)
        return first;
      else if(pred(*first))
        ++first;
      else
        break;

    --last;
    while(true)
      if(first == last)
        return first;
      else if(!pred(*last))
       --last;
      else
        break;

    iter_swap(first, last);
    ++first;
  }
}


// stable_partition

template<class ForwardIterator, class Predicate, class Distance>
ForwardIterator
  __inplace_stable_partition
    (ForwardIterator first, ForwardIterator last, Predicate pred, Distance len)
{
  if(len == 1)
    return pred(*first) ? last : first;

  ForwardIterator middle = first;
  advance(middle, len/2);
  ForwardIterator first_cut = __inplace_stable_partition(first, middle, pred, len/2);
  ForwardIterator second_cut = __inplace_stable_partition(middle, last, pred, len-len/2);
  rotate(first_cut, middle, second_cut);

  len = 0;
  distance(middle, second_cut, len);
  advance(first_cut, len);

  return first_cut;
}

template<class ForwardIterator, class Pointer, class Predicate, class Distance, class T>
ForwardIterator
  __stable_partition_adaptive
    (ForwardIterator first, ForwardIterator last,
     Predicate pred, Distance len,
     Pointer buffer, Distance buffer_size,
     Distance& fill_pointer, T*)
{
  if(len <= buffer_size)
  {
    len = 0;
    ForwardIterator result1 = first;
    Pointer result2 = buffer;

    while(first != last && len < fill_pointer)
      if(pred(*first))
        *result1++ = *first++;
      else
      {
        *result2++ = *first++;
        ++len;
      }

    if(first != last)
    {
      raw_storage_iterator<Pointer, T> result3 = result2;
      while(first != last)
        if(pred(*first))
          *result1++ = *first++;
        else
        {
          *result3++ = *first++;
          ++len;
        }

      fill_pointer = len;
    }

    copy(buffer, buffer+len, result1);
    return result1;
  }

  ForwardIterator middle = first;
  advance(middle, len/2);
  ForwardIterator first_cut = __stable_partition_adaptive(first, middle, pred, len/2, buffer, buffer_size, fill_pointer, (T*)0);
  ForwardIterator second_cut = __stable_partition_adaptive(middle, last, pred, len-len/2, buffer, buffer_size, fill_pointer, (T*)0);
  rotate(first_cut, middle, second_cut);

  len = 0;
  distance(middle, second_cut, len);
  advance(first_cut, len);

  return first_cut;
}

template<class ForwardIterator, class Predicate, class Pointer, class Distance>
ForwardIterator
  __stable_partition
    (ForwardIterator first, ForwardIterator last, Predicate pred,
     Distance len, pair<Pointer, Distance> p)
{
  if(p.first == 0)
    return __inplace_stable_partition(first, last, pred, len);

  Distance fill_pointer = 0;
  ForwardIterator result = __stable_partition_adaptive(first, last, pred, len, p.first, p.second, fill_pointer, value_type(first));
  destroy(p.first, p.first+fill_pointer);
  return_temporary_buffer(p.first);
  return result;
}

template<class ForwardIterator, class Predicate, class Distance>
ForwardIterator
  __stable_partition_aux(ForwardIterator first, ForwardIterator last, Predicate pred, Distance*)
{
  Distance len = 0;
  distance(first, last, len);
  return __stable_partition(first, last, pred, len, get_temporary_buffer(len, value_type(first)));
}

template<class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred)
{
  return __stable_partition_aux(first, last, pred, distance_type(first));
}


// sorting and related operations

// sort

template<class RandomAccessIterator, class T>
RandomAccessIterator
  __unguarded_partition(RandomAccessIterator first, RandomAccessIterator last, T pivot)
{
  while(1)
  {
    while(*first < pivot)
      ++first;

    --last;
    while(pivot < *last)
      --last;

    if(!(first < last))
      return first;

    iter_swap(first, last);
    ++first;
  }
}

template<class RandomAccessIterator, class T, class Compare>
RandomAccessIterator
  __unguarded_partition(RandomAccessIterator first, RandomAccessIterator last, T pivot, Compare comp)
{
  while(1)
  {
    while(comp(*first, pivot))
      ++first;

    --last;
    while(comp(pivot, *last))
      --last;

    if(!(first < last))
      return first;

    iter_swap(first, last);
    ++first;
  }
}

static const int __stl_threshold = 16;

template<class T>
T const& __median(T const& a, T const& b, T const& c)
{
  if(a < b)
    if(b < c)
      return b;
    else if(a < c)
      return c;
  else
    return a;
  else if(a < c)
    return a;
  else if(b < c)
    return c;
  else
    return b;
}

template<class T, class Compare>
T const& __median(T const& a, T const& b, T const& c, Compare comp)
{
  if(comp(a, b))
    if(comp(b, c))
      return b;
    else if(comp(a, c))
      return c;
  else
    return a;
  else if(comp(a, c))
    return a;
  else if(comp(b, c))
    return c;
  else
    return b;
}

template<class RandomAccessIterator, class T>
void __quick_sort_loop_aux(RandomAccessIterator first, RandomAccessIterator last, T*)
{
  while(last-first > __stl_threshold)
  {
    RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first+(last-first)/2), *(last-1))));
    if(cut-first >= last-cut)
    {
      __quick_sort_loop_aux(cut, last, (T*)0);
      last = cut;
    }
    else
    {
      __quick_sort_loop_aux(first, cut, (T*)0);
      first = cut;
    }
  }
}

template<class RandomAccessIterator>
inline void __quick_sort_loop(RandomAccessIterator first, RandomAccessIterator last)
{
  __quick_sort_loop_aux(first, last, value_type(first));
}

template<class RandomAccessIterator, class T, class Compare>
void __quick_sort_loop_aux(RandomAccessIterator first, RandomAccessIterator last, T*, Compare comp)
{
  while(last-first > __stl_threshold)
  {
    RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first+(last-first)/2), *(last-1), comp)), comp);
    if(cut-first >= last-cut)
    {
      __quick_sort_loop_aux(cut, last, (T*)0, comp);
      last = cut;
    }
    else
    {
      __quick_sort_loop_aux(first, cut, (T*)0, comp);
      first = cut;
    }
  }
}

template<class RandomAccessIterator, class Compare>
inline void __quick_sort_loop(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  __quick_sort_loop_aux(first, last, value_type(first), comp);
}

template<class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value)
{
  RandomAccessIterator next = last;

  --next;
  while(value < *next)
  {
    *last = *next;
    last = next--;
  }

  *last = value;
}

template<class RandomAccessIterator, class T, class Compare>
void __unguarded_linear_insert(RandomAccessIterator last, T value, Compare comp)
{
  RandomAccessIterator next = last;

  --next;
  while(comp(value , *next))
  {
    *last = *next;
    last = next--;
  }

  *last = value;
}

template<class RandomAccessIterator, class T>
void __linear_insert(RandomAccessIterator first, RandomAccessIterator last, T*)
{
  T value = *last;
  if(value < *first)
  {
    copy_backward(first, last, last+1);
    *first = value;
  }
  else
    __unguarded_linear_insert(last, value);
}

template<class RandomAccessIterator, class T, class Compare>
void __linear_insert(RandomAccessIterator first, RandomAccessIterator last, T*, Compare comp)
{
  T value = *last;
  if(comp(value, *first))
  {
    copy_backward(first, last, last+1);
    *first = value;
  }
  else
    __unguarded_linear_insert(last, value, comp);
}

template<class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
  if(first == last)
    return;

  for(RandomAccessIterator i = first+1; i != last; ++i)
    __linear_insert(first, i, value_type(first));
}

template<class RandomAccessIterator, class Compare>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  if(first == last)
    return;

  for(RandomAccessIterator i = first+1; i != last; ++i)
    __linear_insert(first, i, value_type(first), comp);
}

template<class RandomAccessIterator, class T>
void __unguarded_insertion_sort_aux(RandomAccessIterator first, RandomAccessIterator last, T*)
{
  for(RandomAccessIterator i = first; i != last; ++i)
    __unguarded_linear_insert(i, T(*i));
}

template<class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
  __unguarded_insertion_sort_aux(first, last, value_type(first));
}

template<class RandomAccessIterator, class T, class Compare>
void __unguarded_insertion_sort_aux(RandomAccessIterator first, RandomAccessIterator last, T*, Compare comp)
{
  for(RandomAccessIterator i = first; i != last; ++i)
    __unguarded_linear_insert(i, T(*i), comp);
}

template<class RandomAccessIterator, class Compare>
inline void __unguarded_insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  __unguarded_insertion_sort_aux(first, last, value_type(first), comp);
}

template<class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
  if(last-first > __stl_threshold)
  {
    __insertion_sort(first, first+__stl_threshold);
    __unguarded_insertion_sort(first+__stl_threshold, last);
  }
  else
    __insertion_sort(first, last);
}

template<class RandomAccessIterator, class Compare>
void __final_insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  if(last-first > __stl_threshold)
  {
    __insertion_sort(first, first+__stl_threshold, comp);
    __unguarded_insertion_sort(first+__stl_threshold, last, comp);
  }
  else
    __insertion_sort(first, last, comp);
}

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last)
{
  __quick_sort_loop(first, last);
  __final_insertion_sort(first, last);
}

template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  __quick_sort_loop(first, last, comp);
  __final_insertion_sort(first, last, comp);
}


// stable_sort

template<class RandomAccessIterator>
void __inplace_stable_sort(RandomAccessIterator first, RandomAccessIterator last)
{
  if(last-first < 15)
  {
    __insertion_sort(first, last);
    return;
  }

  RandomAccessIterator middle = first+(last-first)/2;
  __inplace_stable_sort(first, middle);
  __inplace_stable_sort(middle, last);
  __merge_without_buffer(first, middle, last, middle-first, last-middle);
}

template<class RandomAccessIterator, class Compare>
void __inplace_stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  if(last-first < 15)
  {
    __insertion_sort(first, last, comp);
    return;
  }

  RandomAccessIterator middle = first+(last-first)/2;
  __inplace_stable_sort(first, middle, comp);
  __inplace_stable_sort(middle, last, comp);
  __merge_without_buffer(first, middle, last, middle-first, last-middle, comp);
}

template<class RandomAccessIterator1, class RandomAccessIterator2, class Distance>
void
  __merge_sort_loop
    (RandomAccessIterator1 first, RandomAccessIterator1 last, RandomAccessIterator2 result,
     Distance step_size)
{
  Distance two_step = 2*step_size;

  while(last-first >= two_step)
  {
    result = merge(first, first+step_size, first+step_size, first+two_step, result);
    first += two_step;
  }

  step_size = min(Distance(last-first), step_size);
  merge(first, first+step_size, first+step_size, last, result);
}

template<class RandomAccessIterator1, class RandomAccessIterator2, class Distance, class Compare>
void
  __merge_sort_loop
    (RandomAccessIterator1 first, RandomAccessIterator1 last, RandomAccessIterator2 result,
     Distance step_size, Compare comp)
{
  Distance two_step = 2*step_size;

  while(last-first >= two_step)
  {
    result = merge(first, first+step_size, first+step_size, first+two_step, result, comp);
    first += two_step;
  }

  step_size = min(Distance(last-first), step_size);
  merge(first, first+step_size, first+step_size, last, result, comp);
}

static const int __stl_chunk_size = 7;

template<class RandomAccessIterator, class Distance>
void __chunk_insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Distance chunk_size)
{
  while(last-first >= chunk_size)
  {
    __insertion_sort(first, first+chunk_size);
    first += chunk_size;
  }

  __insertion_sort(first, last);
}

template<class RandomAccessIterator, class Distance, class Compare>
void __chunk_insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Distance chunk_size, Compare comp)
{
  while(last-first >= chunk_size)
  {
    __insertion_sort(first, first+chunk_size, comp);
    first += chunk_size;
  }

  __insertion_sort(first, last, comp);
}

template<class RandomAccessIterator, class Pointer, class Distance, class T>
void __merge_sort_with_buffer(RandomAccessIterator first, RandomAccessIterator last, Pointer buffer, Distance*, T*)
{
  Distance len = last-first;
  Pointer buffer_last = buffer+len;

  Distance step_size = __stl_chunk_size;
  __chunk_insertion_sort(first, last, step_size);

  while(step_size < len)
  {
    __merge_sort_loop(first, last, buffer, step_size);
    step_size *= 2;
    __merge_sort_loop(buffer, buffer_last, first, step_size);
    step_size *= 2;
  }
}

template<class RandomAccessIterator, class Pointer, class Distance, class T, class Compare>
void
  __merge_sort_with_buffer
    (RandomAccessIterator first, RandomAccessIterator last, Pointer buffer, Distance*, T*, Compare comp)
{
  Distance len = last-first;
  Pointer buffer_last = buffer+len;

  Distance step_size = __stl_chunk_size;
  __chunk_insertion_sort(first, last, step_size, comp);

  while(step_size < len)
  {
    __merge_sort_loop(first, last, buffer, step_size, comp);
    step_size *= 2;
    __merge_sort_loop(buffer, buffer_last, first, step_size, comp);
    step_size *= 2;
  }
}

template<class RandomAccessIterator, class Pointer, class Distance, class T>
void
  __stable_sort_adaptive
    (RandomAccessIterator first, RandomAccessIterator last, Pointer buffer, Distance buffer_size, T*)
{
  Distance len = (last-first+1)/2;
  RandomAccessIterator middle = first+len;

  if(len > buffer_size)
  {
    __stable_sort_adaptive(first, middle, buffer, buffer_size, (T*)0);
    __stable_sort_adaptive(middle, last, buffer, buffer_size, (T*)0);
  }
  else
  {
    __merge_sort_with_buffer(first, middle, buffer, (Distance*)0, (T*)0);
    __merge_sort_with_buffer(middle, last, buffer, (Distance*)0, (T*)0);
  }

  __merge_adaptive(first, middle, last, Distance(middle-first),
  Distance(last-middle), buffer, buffer_size, (T*)0);
}

template<class RandomAccessIterator, class Pointer, class Distance, class T, class Compare>
void
  __stable_sort_adaptive
    (RandomAccessIterator first, RandomAccessIterator last,
     Pointer buffer, Distance buffer_size, T*, Compare comp)
{
  Distance len = (last-first+1)/2;
  RandomAccessIterator middle = first+len;

  if(len > buffer_size)
  {
    __stable_sort_adaptive(first, middle, buffer, buffer_size, (T*)0, comp);
    __stable_sort_adaptive(middle, last, buffer, buffer_size, (T*)0, comp);
  }
  else
  {
    __merge_sort_with_buffer(first, middle, buffer, (Distance*)0, (T*)0, comp);
    __merge_sort_with_buffer(middle, last, buffer, (Distance*)0, (T*)0, comp);
  }

  __merge_adaptive(first, middle, last, Distance(middle-first),
  Distance(last-middle), buffer, buffer_size, (T*)0, comp);
}

template<class RandomAccessIterator, class Pointer, class Distance, class T>
void
  __stable_sort
    (RandomAccessIterator first, RandomAccessIterator last,
     pair<Pointer, Distance> p, T*)
{
  if(p.first == 0)
  {
    __inplace_stable_sort(first, last);
    return;
  }

  Distance len = min(p.second, Distance(last-first));
  copy(first, first+len, raw_storage_iterator<Pointer, T>(p.first));
  __stable_sort_adaptive(first, last, p.first, p.second, (T*)0);
  destroy(p.first, p.first+len);

  return_temporary_buffer(p.first);
}

template<class RandomAccessIterator, class Pointer, class Distance, class T, class Compare>
void
  __stable_sort
    (RandomAccessIterator first, RandomAccessIterator last,
     pair<Pointer, Distance> p, T*, Compare comp)
{
  if(p.first == 0)
  {
    __inplace_stable_sort(first, last, comp);
    return;
  }

  Distance len = min(p.second, Distance(last-first));
  copy(first, first+len, raw_storage_iterator<Pointer, T>(p.first));
  __stable_sort_adaptive(first, last, p.first, p.second, (T*)0, comp);
  destroy(p.first, p.first+len);

  return_temporary_buffer(p.first);
}

template<class RandomAccessIterator, class T, class Distance>
void
  __stable_sort_aux
    (RandomAccessIterator first, RandomAccessIterator last, T*, Distance*)
{
  __stable_sort(first, last, get_temporary_buffer(Distance(last-first), (T*)0), (T*)0);
}

template<class RandomAccessIterator, class T, class Distance, class Compare>
void
  __stable_sort_aux
    (RandomAccessIterator first, RandomAccessIterator last, T*, Distance*, Compare comp)
{
  __stable_sort(first, last, get_temporary_buffer(Distance(last-first), (T*)0), (T*)0, comp);
}

template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last)
{
  __stable_sort_aux(first, last, value_type(first), distance_type(first));
}

template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  __stable_sort_aux(first, last, value_type(first), distance_type(first), comp);
}


// partial_sort

template<class RandomAccessIterator, class T>
void
  __partial_sort
    (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, T*)
{
  make_heap(first, middle);

  for(RandomAccessIterator i = middle; i < last; ++i)
  if(*i < *first)
    __pop_heap(first, middle, i, T(*i), distance_type(first));

  sort_heap(first, middle);
}

template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
{
  __partial_sort(first, middle, last, value_type(first));
}

template<class RandomAccessIterator, class T, class Compare>
void
  __partial_sort
    (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, T*, Compare comp)
{
  make_heap(first, middle, comp);

  for(RandomAccessIterator i = middle; i < last; ++i)
    if(comp(*i, *first))
      __pop_heap(first, middle, i, T(*i), comp, distance_type(first));

  sort_heap(first, middle, comp);
}

template<class RandomAccessIterator, class Compare>
void
  partial_sort
    (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp)
{
  __partial_sort(first, middle, last, value_type(first), comp);
}

template<class InputIterator, class RandomAccessIterator, class Distance, class T>
RandomAccessIterator
  __partial_sort_copy
    (InputIterator first, InputIterator last,
     RandomAccessIterator result_first, RandomAccessIterator result_last,
     Distance*, T*)
{
  if(result_first == result_last)
    return result_last;

  RandomAccessIterator result_real_last = result_first;
  while(first != last && result_real_last != result_last)
    *result_real_last++ = *first++;

  make_heap(result_first, result_real_last);
  while(first != last)
  {
    if(*first < *result_first)
      __adjust_heap(result_first, Distance(0),

    Distance(result_real_last-result_first), T(*first));
    ++first;
  }

  sort_heap(result_first, result_real_last);
  return result_real_last;
}

template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
  partial_sort_copy
    (InputIterator first, InputIterator last,
     RandomAccessIterator result_first, RandomAccessIterator result_last)
{
  return __partial_sort_copy(first, last, result_first, result_last, distance_type(result_first), value_type(first));
}

template<class InputIterator, class RandomAccessIterator, class Compare, class Distance, class T>
RandomAccessIterator
  __partial_sort_copy
    (InputIterator first, InputIterator last,
     RandomAccessIterator result_first, RandomAccessIterator result_last,
     Compare comp, Distance*, T*)
{
  if(result_first == result_last)
    return result_last;

  RandomAccessIterator result_real_last = result_first;
  while(first != last && result_real_last != result_last)
    *result_real_last++ = *first++;

  make_heap(result_first, result_real_last, comp);
  while(first != last)
  {
    if(comp(*first, *result_first))
      __adjust_heap(result_first, Distance(0),

    Distance(result_real_last-result_first), T(*first), comp);
    ++first;
  }

  sort_heap(result_first, result_real_last, comp);
  return result_real_last;
}

template<class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator
  partial_sort_copy
    (InputIterator first, InputIterator last,
     RandomAccessIterator result_first, RandomAccessIterator result_last,
     Compare comp)
{
  return __partial_sort_copy(first, last, result_first, result_last, comp, distance_type(result_first), value_type(first));
}


// Nth element

template<class RandomAccessIterator, class T>
void
  __nth_element
    (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, T*)
{
    while(last-first > 3)
  {
    RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first+(last-first)/2), *(last-1))));
    if(cut <= nth)
      first = cut;
    else
      last = cut;
  }

  __insertion_sort(first, last);
}

template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
{
  __nth_element(first, nth, last, value_type(first));
}

template<class RandomAccessIterator, class T, class Compare>
void
  __nth_element
    (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last,
     T*, Compare comp)
{
    while(last-first > 3)
  {
    RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first+(last-first)/2), *(last-1), comp)), comp);
    if(cut <= nth)
      first = cut;
    else
      last = cut;
  }

  __insertion_sort(first, last, comp);
}

template<class RandomAccessIterator, class Compare>
void
  nth_element
    (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp)
{
  __nth_element(first, nth, last, value_type(first), comp);
}


// binary search

// lower_bound

template<class ForwardIterator, class T, class Distance>
ForwardIterator
  __lower_bound
    (ForwardIterator first, ForwardIterator last, T const& value, Distance*, forward_iterator_tag)
{
  Distance len = 0;
  distance(first, last, len);
  Distance half;
  ForwardIterator middle;

    while(len > 0)
  {
    half = len/2;
    middle = first;
    advance(middle, half);
    if(*middle < value)
    {
      first = middle;
      ++first;
      len = len-half-1;
    }
    else
      len = half;
  }
  return first;
}

template<class ForwardIterator, class T, class Distance>
inline ForwardIterator
  __lower_bound
    (ForwardIterator first, ForwardIterator last,
     T const& value, Distance*, bidirectional_iterator_tag)
{
  return __lower_bound(first, last, value, (Distance*)0, forward_iterator_tag());
}

template<class RandomAccessIterator, class T, class Distance>
RandomAccessIterator
  __lower_bound
    (RandomAccessIterator first, RandomAccessIterator last, T const& value,
     Distance*, random_access_iterator_tag)
{
  Distance len = last-first;
  Distance half;
  RandomAccessIterator middle;

    while(len > 0)
  {
    half = len/2;
    middle = first+half;
    if(*middle < value)
    {
      first = middle+1;
      len = len-half-1;
    }
    else
      len = half;
  }

  return first;
}

template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, T const& value)
{
  return __lower_bound(first, last, value, distance_type(first), iterator_category(first));
}

template<class ForwardIterator, class T, class Compare, class Distance>
ForwardIterator
  __lower_bound
    (ForwardIterator first, ForwardIterator last, T const& value, Compare comp,
     Distance*, forward_iterator_tag)
{
  Distance len = 0;
  distance(first, last, len);
  Distance half;
  ForwardIterator middle;

    while(len > 0)
  {
    half = len/2;
    middle = first;
    advance(middle, half);
    if(comp(*middle, value))
    {
      first = middle;
      ++first;
      len = len-half-1;
    }
    else
      len = half;
  }

  return first;
}

template<class ForwardIterator, class T, class Compare, class Distance>
inline ForwardIterator
  __lower_bound
    (ForwardIterator first, ForwardIterator last,
     T const& value, Compare comp, Distance*, bidirectional_iterator_tag)
{
  return __lower_bound(first, last, value, comp, (Distance*)0, forward_iterator_tag());
}

template<class RandomAccessIterator, class T, class Compare, class Distance>
RandomAccessIterator
  __lower_bound
    (RandomAccessIterator first, RandomAccessIterator last,
     T const& value, Compare comp, Distance*, random_access_iterator_tag)
{
  Distance len = last-first;
  Distance half;
  RandomAccessIterator middle;

    while(len > 0)
  {
    half = len/2;
    middle = first+half;
    if(comp(*middle, value))
    {
      first = middle+1;
      len = len-half-1;
    }
    else
      len = half;
  }

  return first;
}

template<class ForwardIterator, class T, class Compare>
ForwardIterator
  lower_bound(ForwardIterator first, ForwardIterator last, T const& value, Compare comp)
{
  return __lower_bound(first, last, value, comp, distance_type(first), iterator_category(first));
}


// upper_bound

template<class ForwardIterator, class T, class Distance>
ForwardIterator
  __upper_bound
    (ForwardIterator first, ForwardIterator last, T const& value,
     Distance*, forward_iterator_tag)
{
  Distance len = 0;
  distance(first, last, len);
  Distance half;
  ForwardIterator middle;

    while(len > 0)
  {
    half = len/2;
    middle = first;
    advance(middle, half);
    if(value < *middle)
      len = half;
    else
    {
      first = middle;
      ++first;
      len = len-half-1;
    }
  }

  return first;
}

template<class ForwardIterator, class T, class Distance>
inline ForwardIterator
  __upper_bound
    (ForwardIterator first, ForwardIterator last,
     T const& value, Distance*, bidirectional_iterator_tag)
{
  return __upper_bound(first, last, value, (Distance*)0, forward_iterator_tag());
}

template<class RandomAccessIterator, class T, class Distance>
RandomAccessIterator
  __upper_bound
    (RandomAccessIterator first, RandomAccessIterator last, T const& value,
     Distance*, random_access_iterator_tag)
{
  Distance len = last-first;
  Distance half;
  RandomAccessIterator middle;

    while(len > 0)
  {
    half = len/2;
    middle = first+half;
    if(value < *middle)
      len = half;
    else
    {
      first = middle+1;
      len = len-half-1;
    }
  }

  return first;
}

template<class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, T const& value)
{
  return __upper_bound(first, last, value, distance_type(first), iterator_category(first));
}

template<class ForwardIterator, class T, class Compare, class Distance>
ForwardIterator
  __upper_bound
    (ForwardIterator first, ForwardIterator last, T const& value,
     Compare comp, Distance*, forward_iterator_tag)
{
  Distance len = 0;
  distance(first, last, len);
  Distance half;
  ForwardIterator middle;

    while(len > 0)
  {
    half = len/2;
    middle = first;
    advance(middle, half);
    if(comp(value, *middle))
      len = half;
    else
    {
      first = middle;
      ++first;
      len = len-half-1;
    }

  }

  return first;
}

template<class ForwardIterator, class T, class Compare, class Distance>
inline ForwardIterator
  __upper_bound
    (ForwardIterator first, ForwardIterator last,
     T const& value, Compare comp, Distance*, bidirectional_iterator_tag)
{
  return __upper_bound(first, last, value, comp, (Distance*)0, forward_iterator_tag());
}

template<class RandomAccessIterator, class T, class Compare, class Distance>
RandomAccessIterator
  __upper_bound
    (RandomAccessIterator first, RandomAccessIterator last, T const& value,
     Compare comp, Distance*, random_access_iterator_tag)
{
  Distance len = last-first;
  Distance half;
  RandomAccessIterator middle;

    while(len > 0)
  {
    half = len/2;
    middle = first+half;
    if(comp(value, *middle))
      len = half;
    else
    {
      first = middle+1;
      len = len-half-1;
    }
  }

  return first;
}

template<class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, T const& value, Compare comp)
{
  return __upper_bound(first, last, value, comp, distance_type(first), iterator_category(first));
}


// equal_range

template<class ForwardIterator, class T, class Distance>
pair<ForwardIterator, ForwardIterator>
  __equal_range
    (ForwardIterator first, ForwardIterator last, T const& value,
     Distance*, forward_iterator_tag)
{
  Distance len = 0;
  distance(first, last, len);
  Distance half;
  ForwardIterator middle, left, right;

    while(len > 0)
  {
    half = len/2;
    middle = first;
    advance(middle, half);
    if(*middle < value)
    {
      first = middle;
      ++first;
      len = len-half-1;
    }
    else if(value < *middle)
      len = half;
    else
    {
      left = lower_bound(first, middle, value);
      advance(first, len);
      right = upper_bound(++middle, first, value);
      return pair<ForwardIterator, ForwardIterator>(left, right);
    }
  }

  return pair<ForwardIterator, ForwardIterator>(first, first);
}

template<class ForwardIterator, class T, class Distance>
inline pair<ForwardIterator, ForwardIterator>
  __equal_range
    (ForwardIterator first, ForwardIterator last,
     T const& value, Distance*, bidirectional_iterator_tag)
{
  return __equal_range(first, last, value, (Distance*)0, forward_iterator_tag());
}

template<class RandomAccessIterator, class T, class Distance>
pair<RandomAccessIterator, RandomAccessIterator>
  __equal_range
    (RandomAccessIterator first, RandomAccessIterator last, T const& value,
     Distance*, random_access_iterator_tag)
{
  Distance len = last-first;
  Distance half;
  RandomAccessIterator middle, left, right;

    while(len > 0)
  {
    half = len/2;
    middle = first+half;
    if(*middle < value)
    {
      first = middle+1;
      len = len-half-1;
    }
    else if(value < *middle)
      len = half;
    else
    {
      left = lower_bound(first, middle, value);
      right = upper_bound(++middle, first+len, value);
      return pair<RandomAccessIterator, RandomAccessIterator>(left, right);
    }
  }

  return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
}

template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
  equal_range(ForwardIterator first, ForwardIterator last, T const& value)
{
  return __equal_range(first, last, value, distance_type(first), iterator_category(first));
}

template<class ForwardIterator, class T, class Compare, class Distance>
pair<ForwardIterator, ForwardIterator>
  __equal_range
    (ForwardIterator first, ForwardIterator last, T const& value,
     Compare comp, Distance*, forward_iterator_tag)
{
  Distance len = 0;
  distance(first, last, len);
  Distance half;
  ForwardIterator middle, left, right;

    while(len > 0)
  {
    half = len/2;
    middle = first;
    advance(middle, half);

    if(comp(*middle, value))
    {
      first = middle;
      ++first;
      len = len-half-1;
    }
    else if(comp(value, *middle))
      len = half;
    else
    {
      left = lower_bound(first, middle, value, comp);
      advance(first, len);
      right = upper_bound(++middle, first, value, comp);
      return pair<ForwardIterator, ForwardIterator>(left, right);
    }
  }

  return pair<ForwardIterator, ForwardIterator>(first, first);
}

template<class ForwardIterator, class T, class Compare, class Distance>
inline pair<ForwardIterator, ForwardIterator>
  __equal_range
    (ForwardIterator first, ForwardIterator last,
     T const& value, Compare comp, Distance*, bidirectional_iterator_tag)
{
  return __equal_range(first, last, value, comp, (Distance*)0, forward_iterator_tag());
}

template<class RandomAccessIterator, class T, class Compare, class Distance>
pair<RandomAccessIterator, RandomAccessIterator>
  __equal_range
    (RandomAccessIterator first, RandomAccessIterator last, T const& value,
     Compare comp, Distance*, random_access_iterator_tag)
{
  Distance len = last-first;
  Distance half;
  RandomAccessIterator middle, left, right;

    while(len > 0)
  {
    half = len/2;
    middle = first+half;
    if(comp(*middle, value))
    {
      first = middle+1;
      len = len-half-1;
    }
    else if(comp(value, *middle))
      len = half;
    else
    {
      left = lower_bound(first, middle, value, comp);
      right = upper_bound(++middle, first+len, value, comp);
      return pair<RandomAccessIterator, RandomAccessIterator>(left, right);
    }
  }


  return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
}

template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
  equal_range(ForwardIterator first, ForwardIterator last, T const& value, Compare comp)
{
  return __equal_range(first, last, value, comp, distance_type(first), iterator_category(first));
}


// binary_search

template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, T const& value)
{
  ForwardIterator i = lower_bound(first, last, value);
  return i != last && !(value < *i);
}

template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, T const& value, Compare comp)
{
  ForwardIterator i = lower_bound(first, last, value, comp);
  return i != last && !comp(value, *i);
}


// merge

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge
  (InputIterator1 first1, InputIterator1 last1,
   InputIterator2 first2, InputIterator2 last2,
   OutputIterator result)
{
  while(first1 != last1 && first2 != last2)
    if(*first2 < *first1)
      *result++ = *first2++;
    else
      *result++ = *first1++;

  return copy(first2, last2, copy(first1, last1, result));
}

template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator merge
  (InputIterator1 first1, InputIterator1 last1,
   InputIterator2 first2, InputIterator2 last2,
   OutputIterator result, Compare comp)
{
  while(first1 != last1 && first2 != last2)
    if(comp(*first2, *first1))
      *result++ = *first2++;
    else
      *result++ = *first1++;

  return copy(first2, last2, copy(first1, last1, result));
}


// inplace_merge

template<class BidirectionalIterator, class Distance>
void
  __merge_without_buffer
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
     Distance len1, Distance len2)
{
  if(len1 == 0 || len2 == 0)
    return;

  if(len1+len2 == 2)
  {
    if(*middle < *first)
      iter_swap(first, middle);

    return;
  }

  BidirectionalIterator first_cut = first;
  BidirectionalIterator second_cut = middle;
  Distance len11 = 0;
  Distance len22 = 0;

  if(len1 > len2)
  {
    len11 = len1/2;
    advance(first_cut, len11);
    second_cut = lower_bound(middle, last, *first_cut);
    distance(middle, second_cut, len22);
  }
  else
  {
    len22 = len2/2;
    advance(second_cut, len22);
    first_cut = upper_bound(first, middle, *second_cut);
    distance(first, first_cut, len11);
  }

  rotate(first_cut, middle, second_cut);
  BidirectionalIterator new_middle = first_cut;
  advance(new_middle, len22);
  __merge_without_buffer(first, first_cut, new_middle, len11, len22);
  __merge_without_buffer(new_middle, second_cut, last, len1-len11, len2-len22);
}

template<class BidirectionalIterator, class Distance, class Compare>
void
  __merge_without_buffer
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
     Distance len1, Distance len2, Compare comp)
{
  if(len1 == 0 || len2 == 0)
    return;

  if(len1+len2 == 2)
  {
    if(comp(*middle, *first)) iter_swap(first, middle);
    return;
  }

  BidirectionalIterator first_cut = first;
  BidirectionalIterator second_cut = middle;
  Distance len11 = 0;
  Distance len22 = 0;

  if(len1 > len2)
  {
    len11 = len1/2;
    advance(first_cut, len11);
    second_cut = lower_bound(middle, last, *first_cut, comp);
    distance(middle, second_cut, len22);
  }
  else
  {
    len22 = len2/2;
    advance(second_cut, len22);
    first_cut = upper_bound(first, middle, *second_cut, comp);
    distance(first, first_cut, len11);
  }

  rotate(first_cut, middle, second_cut);
  BidirectionalIterator new_middle = first_cut;
  advance(new_middle, len22);
  __merge_without_buffer(first, first_cut, new_middle, len11, len22, comp);
  __merge_without_buffer(new_middle, second_cut, last, len1-len11, len2-len22, comp);
}

template<class BidirectionalIterator1, class BidirectionalIterator2, class Distance>
BidirectionalIterator1
  __rotate_adaptive
    (BidirectionalIterator1 first, BidirectionalIterator1 middle, BidirectionalIterator1 last,
     Distance len1, Distance len2,
     BidirectionalIterator2 buffer, Distance buffer_size)
{
  BidirectionalIterator2 buffer_end;
  if(len1 > len2 && len2 <= buffer_size)
  {
    buffer_end = copy(middle, last, buffer);
    copy_backward(first, middle, last);
     return copy(buffer, buffer_end, first);
  }
  else if(len1 <= buffer_size)
  {
    buffer_end = copy(first, middle, buffer);
    copy(middle, last, first);
    return copy_backward(buffer, buffer_end, last);
  }
  else
  {
    rotate(first, middle, last);
    advance(first, len2);
    return first;
  }
}

template<class BidirectionalIterator1, class BidirectionalIterator2, class BidirectionalIterator3>
BidirectionalIterator3
  __merge_backward
    (BidirectionalIterator1 first1, BidirectionalIterator1 last1,
     BidirectionalIterator2 first2, BidirectionalIterator2 last2,
     BidirectionalIterator3 result)
{
  if(first1 == last1)
    return copy_backward(first2, last2, result);

  if(first2 == last2)
    return copy_backward(first1, last1, result);

  --last1;
  --last2;

  while(true)
  {
    if(*last2 < *last1)
    {
      *--result = *last1;
      if(first1 == last1)
        return copy_backward(first2, ++last2, result);
      --last1;
    }
    else
    {
      *--result = *last2;
      if(first2 == last2) return copy_backward(first1, ++last1, result);
      --last2;
    }
  }
}

template<class BidirectionalIterator1, class BidirectionalIterator2, class BidirectionalIterator3, class Compare>
BidirectionalIterator3
  __merge_backward
    (BidirectionalIterator1 first1, BidirectionalIterator1 last1,
     BidirectionalIterator2 first2, BidirectionalIterator2 last2,
     BidirectionalIterator3 result,
     Compare comp)
{
  if(first1 == last1)
    return copy_backward(first2, last2, result);

  if(first2 == last2)
    return copy_backward(first1, last1, result);

  --last1;
  --last2;

  while(true)
  {
    if(comp(*last2, *last1))
    {
      *--result = *last1;
      if(first1 == last1) return copy_backward(first2, ++last2, result);
      --last1;
    }
    else
    {
      *--result = *last2;
      if(first2 == last2) return copy_backward(first1, ++last1, result);
      --last2;
    }
  }
}

template<class BidirectionalIterator, class Distance, class Pointer, class T>
void
  __merge_adaptive
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
     Distance len1, Distance len2,
     Pointer buffer, Distance buffer_size, T*)
{
  if(len1 <= len2 && len1 <= buffer_size)
  {
    Pointer end_buffer = copy(first, middle, buffer);
    merge(buffer, end_buffer, middle, last, first);
  }
  else if(len2 <= buffer_size)
  {
    Pointer end_buffer = copy(middle, last, buffer);
    __merge_backward(first, middle, buffer, end_buffer, last);
  }
  else
  {
    BidirectionalIterator first_cut = first;
    BidirectionalIterator second_cut = middle;
    Distance len11 = 0;
    Distance len22 = 0;

    if(len1 > len2)
    {
      len11 = len1/2;
      advance(first_cut, len11);
      second_cut = lower_bound(middle, last, *first_cut);
      distance(middle, second_cut, len22);
    }
    else
    {
      len22 = len2/2;
      advance(second_cut, len22);
      first_cut = upper_bound(first, middle, *second_cut);
      distance(first, first_cut, len11);
    }

    BidirectionalIterator new_middle = __rotate_adaptive(first_cut, middle, second_cut, len1-len11, len22, buffer, buffer_size);
    __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer, buffer_size, (T*)0);
    __merge_adaptive(new_middle, second_cut, last, len1-len11, len2-len22, buffer, buffer_size, (T*)0);
  }
}

template<class BidirectionalIterator, class Distance, class Pointer, class T, class Compare>
void
  __merge_adaptive
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
     Distance len1, Distance len2,
     Pointer buffer, Distance buffer_size, T*,
     Compare comp)
{
  if(len1 <= len2 && len1 <= buffer_size)
  {
    Pointer end_buffer = copy(first, middle, buffer);
    merge(buffer, end_buffer, middle, last, first, comp);
  }
  else if(len2 <= buffer_size)
  {
    Pointer end_buffer = copy(middle, last, buffer);
    __merge_backward(first, middle, buffer, end_buffer, last, comp);
  }
  else
  {
    BidirectionalIterator first_cut = first;
    BidirectionalIterator second_cut = middle;
    Distance len11 = 0;
    Distance len22 = 0;

    if(len1 > len2)
    {
      len11 = len1/2;
      advance(first_cut, len11);
      second_cut = lower_bound(middle, last, *first_cut, comp);
      distance(middle, second_cut, len22);
    }
    else
    {
      len22 = len2/2;
      advance(second_cut, len22);
      first_cut = upper_bound(first, middle, *second_cut, comp);
      distance(first, first_cut, len11);
    }

    BidirectionalIterator new_middle = __rotate_adaptive(first_cut, middle, second_cut, len1-len11, len22, buffer, buffer_size);
    __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer, buffer_size, (T*)0, comp);
    __merge_adaptive(new_middle, second_cut, last, len1-len11, len2-len22, buffer, buffer_size, (T*)0, comp);
  }
}

template<class BidirectionalIterator, class Distance, class Pointer, class T>
void
  __inplace_merge
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
     Distance len1, Distance len2,
     pair<Pointer, Distance> p, T*)
{
  if(p.first == 0)
  {
    __merge_without_buffer(first, middle, last, len1, len2);
    return;
  }

  Distance len = min(p.second, Distance(len1+len2));
  fill_n(raw_storage_iterator<Pointer, T>(p.first), len, *first);
  __merge_adaptive(first, middle, last, len1, len2, p.first, p.second, (T*)0);
  destroy(p.first, p.first+len);
  return_temporary_buffer(p.first);
}

template<class BidirectionalIterator, class Distance, class Pointer, class T, class Compare>
void
  __inplace_merge
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
     Distance len1, Distance len2,
     pair<Pointer, Distance> p, T*,
     Compare comp)
{
  if(p.first == 0)
  {
    __merge_without_buffer(first, middle, last, len1, len2, comp);
    return;
  }

  Distance len = min(p.second, Distance(len1+len2));
  fill_n(raw_storage_iterator<Pointer, T>(p.first), len, *first);
  __merge_adaptive(first, middle, last, len1, len2, p.first, p.second, (T*)0, comp);
  destroy(p.first, p.first+len);
  return_temporary_buffer(p.first);
}

template<class BidirectionalIterator, class T, class Distance>
void
  __inplace_merge_aux
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
     T*, Distance*)
{
  Distance len1 = 0;
  distance(first, middle, len1);
  Distance len2 = 0;
  distance(middle, last, len2);
  __inplace_merge(first, middle, last, len1, len2, get_temporary_buffer(len1+len2, (T*)0), (T*)0);
}

template<class BidirectionalIterator, class T, class Distance, class Compare>
void
  __inplace_merge_aux
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
     T*, Distance*, Compare comp)
{
  Distance len1 = 0;
  distance(first, middle, len1);
  Distance len2 = 0;
  distance(middle, last, len2);
  __inplace_merge(first, middle, last, len1, len2, get_temporary_buffer(len1+len2, (T*)0), (T*)0, comp);
}

template<class BidirectionalIterator>
void
  inplace_merge
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last)
{
  if(first == middle || middle == last)
    return;
  __inplace_merge_aux(first, middle, last, value_type(first), distance_type(first));
}

template<class BidirectionalIterator, class Compare>
void
  inplace_merge
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
     Compare comp)
{
  if(first == middle || middle == last)
    return;

  __inplace_merge_aux(first, middle, last, value_type(first), distance_type(first), comp);
}


// set operations on sorted structures

// includes

template<class InputIterator1, class InputIterator2>
bool
  includes
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2)
{
  while(first1 != last1 && first2 != last2)
    if(*first2 < *first1)
      return false;
    else if(*first1 < *first2)
      ++first1;
    else
      ++first1, ++first2;

  return first2 == last2;
}

template<class InputIterator1, class InputIterator2, class Compare>
bool
  includes
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     Compare comp)
{
  while(first1 != last1 && first2 != last2)
    if(comp(*first2, *first1))
      return false;
    else if(comp(*first1, *first2))
      ++first1;
    else
      ++first1, ++first2;

  return first2 == last2;
}


// set_union

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
  set_union
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result)
{
  while(first1 != last1 && first2 != last2)
    if(*first1 < *first2)
      *result++ = *first1++;
    else if(*first2 < *first1)
      *result++ = *first2++;
    else
    {
      *result++ = *first1++;
      first2++;
    }

  return copy(first2, last2, copy(first1, last1, result));
}

template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
  set_union
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result,
     Compare comp)
{
  while(first1 != last1 && first2 != last2)
    if(comp(*first1, *first2))
      *result++ = *first1++;
    else if(comp(*first2, *first1))
      *result++ = *first2++;
    else
    {
      *result++ = *first1++;
      ++first2;
    }

  return copy(first2, last2, copy(first1, last1, result));
}


// set_intersection

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
  set_intersection
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result)
{
  while(first1 != last1 && first2 != last2)
    if(*first1 < *first2)
      ++first1;
    else if(*first2 < *first1)
      ++first2;
    else
    {
      *result++ = *first1++;
      ++first2;
    }

  return result;
}

template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
  set_intersection
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result,
     Compare comp)
{
  while(first1 != last1 && first2 != last2)
    if(comp(*first1, *first2))
      ++first1;
    else if(comp(*first2, *first1))
      ++first2;
    else
    {
      *result++ = *first1++;
      ++first2;
    }

  return result;
}


// set_difference

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
  set_difference
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result)
{
  while(first1 != last1 && first2 != last2)
    if(*first1 < *first2)
      *result++ = *first1++;
    else if(*first2 < *first1)
      ++first2;
    else
    {
      ++first1;
      ++first2;
    }

  return copy(first1, last1, result);
}

template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
  set_difference
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result,
     Compare comp)
{
  while(first1 != last1 && first2 != last2)
     if(comp(*first1, *first2))
      *result++ = *first1++;
    else if(comp(*first2, *first1))
      ++first2;
    else
    {
      ++first1;
      ++first2;
    }

  return copy(first1, last1, result);
}


// set_symmetric_difference

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
  set_symmetric_difference
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result)
{
  while(first1 != last1 && first2 != last2)
    if(*first1 < *first2)
      *result++ = *first1++;
    else if(*first2 < *first1)
      *result++ = *first2++;
    else
    {
      ++first1;
      ++first2;
    }

  return copy(first2, last2, copy(first1, last1, result));
}

template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
  set_symmetric_difference
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result,
     Compare comp)
{
  while(first1 != last1 && first2 != last2)
    if(comp(*first1, *first2))
      *result++ = *first1++;
    else if(comp(*first2, *first1))
      *result++ = *first2++;
    else
    {
      ++first1;
      ++first2;
    }

  return copy(first2, last2, copy(first1, last1, result));
}


// Implementation of heap operations

template<class RandomAccessIterator, class Distance, class T>
void __push_heap(RandomAccessIterator first, Distance hole_index, Distance top_index, T value)
{
  Distance parent = (hole_index-1)/2;
  while(hole_index > top_index && *(first+parent) < value)
  {
    *(first+hole_index) = *(first+parent);
    hole_index = parent;
    parent = (hole_index-1)/2;
  }
  *(first+hole_index) = value;
}

template<class RandomAccessIterator, class T>
void
  __push_heap_aux(RandomAccessIterator first, RandomAccessIterator last, T*)
{
  __push_heap(first, (last-first)-1, 0, T(*(last-1)));
}

template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last)
{
  __push_heap_aux(first, last, value_type(first));
}

template<class RandomAccessIterator, class Distance, class T, class Compare>
void __push_heap(RandomAccessIterator first, Distance hole_index, Distance top_index, T value, Compare comp)
{
  Distance parent = (hole_index-1)/2;

  while(hole_index > top_index && comp(*(first+parent), value))
  {
    *(first+hole_index) = *(first+parent);
    hole_index = parent;
    parent = (hole_index-1)/2;
  }
  *(first+hole_index) = value;
}

template<class RandomAccessIterator, class Compare,  class T>
void
  __push_heap_aux(RandomAccessIterator first, RandomAccessIterator last, Compare comp, T*)
{
  __push_heap(first, (last-first)-1, 0, T(*(last-1)), comp);
}

template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  __push_heap_aux(first, last, comp, value_type(first));
}

template<class RandomAccessIterator, class Distance, class T>
void __adjust_heap(RandomAccessIterator first, Distance hole_index, Distance len, T value)
{
  Distance top_index = hole_index;
  Distance second_child = 2*hole_index+2;
  while(second_child < len)
  {
    if(*(first+second_child) < *(first+(second_child-1)))
      second_child--;
    *(first+hole_index) = *(first+second_child);
    hole_index = second_child;
    second_child = 2*(second_child+1);
  }
  if(second_child == len)
  {
    *(first+hole_index) = *(first+(second_child-1));
    hole_index = second_child-1;
  }
  __push_heap(first, hole_index, top_index, value);
}

template<class RandomAccessIterator, class T, class Distance>
void
  __pop_heap
    (RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result,
     T value, Distance*)
{
  *result = *first;
  __adjust_heap(first, Distance(0), Distance(last-first), value);
}

template<class RandomAccessIterator, class T>
void
  __pop_heap_aux(RandomAccessIterator first, RandomAccessIterator last, T*)
{
  __pop_heap(first, last-1, last-1, T(*(last-1)), distance_type(first));
}

template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last)
{
  __pop_heap_aux(first, last, value_type(first));
}

template<class RandomAccessIterator, class Distance, class T, class Compare>
void __adjust_heap(RandomAccessIterator first, Distance hole_index, Distance len, T value, Compare comp)
{
  Distance top_index = hole_index;
  Distance second_child = 2*hole_index+2;
  while(second_child < len)
  {
    if(comp(*(first+second_child), *(first+(second_child-1))))
      second_child--;
    *(first+hole_index) = *(first+second_child);
    hole_index = second_child;
    second_child = 2*(second_child+1);
  }
  if(second_child == len)
  {
    *(first+hole_index) = *(first+(second_child-1));
    hole_index = second_child-1;
  }
  __push_heap(first, hole_index, top_index, value, comp);
}

template<class RandomAccessIterator, class T, class Compare, class Distance>
void
  __pop_heap
    (RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result,
     T value, Compare comp, Distance*)
{
  *result = *first;
  __adjust_heap(first, Distance(0), Distance(last-first), value, comp);
}

template<class RandomAccessIterator, class T, class Compare>
void
  __pop_heap_aux(RandomAccessIterator first, RandomAccessIterator last, T*, Compare comp)
{
  __pop_heap(first, last-1, last-1, T(*(last-1)), comp, distance_type(first));
}

template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  __pop_heap_aux(first, last, value_type(first), comp);
}

template<class RandomAccessIterator, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*, Distance*)
{
  if(last-first < 2)
    return;
  Distance len = last-first;
  Distance parent = (len-2)/2;

  while(true)
  {
    __adjust_heap(first, parent, len, T(*(first+parent)));
    if(parent == 0)
      return;
    parent--;
  }
}

template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last)
{
  __make_heap(first, last, value_type(first), distance_type(first));
}

template<class RandomAccessIterator, class Compare, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp, T*, Distance*)
{
  if(last-first < 2)
    return;
  Distance len = last-first;
  Distance parent = (len-2)/2;

  while(true)
  {
    __adjust_heap(first, parent, len, T(*(first+parent)), comp);
    if(parent == 0)
    return;
    parent--;
  }
}

template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  __make_heap(first, last, comp, value_type(first), distance_type(first));
}

template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last)
{
  while(last-first > 1)
    pop_heap(first, last--);
}

template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  while(last-first > 1)
    pop_heap(first, last--, comp);
}


// minimum and maximum

template<class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last)
{
  if(first == last)
    return first;

  ForwardIterator result = first;
  while(++first != last)
    if(*result < *first)
      result = first;

  return result;
}

template<class ForwardIterator, class Compare>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp)
{
  if(first == last)
    return first;

  ForwardIterator result = first;
  while(++first != last)
    if(comp(*result, *first))
      result = first;

  return result;
}

template<class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last)
{
  if(first == last)
    return first;

  ForwardIterator result = first;
  while(++first != last)
    if(*first < *result)
      result = first;

  return result;
}

template<class ForwardIterator, class Compare>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp)
{
  if(first == last)
    return first;

  ForwardIterator result = first;
  while(++first != last)
    if(comp(*first, *result))
      result = first;

  return result;
}


// permutation generators

template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
  if(first == last)
    return false;

  BidirectionalIterator i = first;
  ++i;
  if(i == last)
    return false;

  i = last;
  --i;

  for(;;)
  {
    BidirectionalIterator ii = i--;

    if(*i < *ii)
    {
      BidirectionalIterator j = last;
      while(!(*i < *--j));

      iter_swap(i, j);
      reverse(ii, last);
      return true;
    }

    if(i == first)
    {
      reverse(first, last);
      return false;
    }
  }
}

template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
{
  if(first == last)
    return false;

  BidirectionalIterator i = first;
  ++i;

  if(i == last)
    return false;

  i = last;
  --i;

  for(;;)
  {
    BidirectionalIterator ii = i--;

    if(comp(*i, *ii))
    {
      BidirectionalIterator j = last;
      while(!comp(*i, *--j));

      iter_swap(i, j);
      reverse(ii, last);
      return true;
    }
    if(i == first)
    {
      reverse(first, last);
      return false;
    }
  }
}

template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
  if(first == last)
    return false;

  BidirectionalIterator i = first;
  ++i;

  if(i == last)
    return false;

  i = last;
  --i;

  for(;;)
  {
    BidirectionalIterator ii = i--;

    if(*ii < *i)
    {
      BidirectionalIterator j = last;
      while(!(*--j < *i));

      iter_swap(i, j);
      reverse(ii, last);
      return true;
    }
    if(i == first)
    {
      reverse(first, last);
      return false;
    }
  }
}

template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
{
  if(first == last)
    return false;

  BidirectionalIterator i = first;
  ++i;

  if(i == last)
    return false;

  i = last;
  --i;

  for(;;)
  {
    BidirectionalIterator ii = i--;

    if(comp(*ii, *i))
    {
      BidirectionalIterator j = last;
      while(!comp(*--j, *i));

      iter_swap(i, j);
      reverse(ii, last);
      return true;
    }
    if(i == first)
    {
      reverse(first, last);
      return false;
    }
  }
}
